//给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 
//
// 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 
//
// 
//
// 示例: 
//
// 给定 1->2->3->4, 你应该返回 2->1->4->3.
// 
// Related Topics 链表 
// 👍 618 👎 0

package leetcode.editor.cn;

import common.bean.ListNode;
import common.util.MyUtil;

/**
 * Java：两两交换链表中的节点
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P24_SwapNodesInPairs {
    public static void main(String[] args) {
        Solution solution = new P24_SwapNodesInPairs().new Solution();
        MyUtil.printListNode(solution.swapPairs(MyUtil.createNode(1, 2, 3, 4, 5, 6, 7, 8, 9)));

    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 迭代
     * 核心思想
     * 1、增加虚拟头节点0， 0->1->2->3->4
     * 2、顺序 0->2, 1->3, 2->1
     */
    //class Solution {
    //    public ListNode swapPairs(ListNode head) {
    //        // 0->1->2->3->4
    //        ListNode preHead = new ListNode(0);
    //        preHead.next = head;
    //        for(ListNode l1 = preHead, l2 = l1.next;l2 != null && l2.next != null;) {
    //            ListNode t1 = l2.next;
    //            ListNode t2 = l2.next.next;
    //            l1.next = t1;
    //            l2.next = t2;
    //            t1.next = l2;
    //            l1 = l2;
    //            l2 = t2;
    //        }
    //        return preHead.next;
    //    }
    //}

    /**
     * 递归
     */
    class Solution {
        public ListNode swapPairs(ListNode head) {
            while (head == null || head.next == null) {
                return head;
            }
            ListNode node = head.next;
            head.next = swapPairs(node.next);
            node.next = head;
            return node;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}